package com.example.leetcode.trainingcamp.week2.practice;

/**
 * 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
 *
 * <p>请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/odd-even-linked-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Test328 {
   // 1 2 3 4 5
    public ListNode oddEvenList(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode pre = head;
        ListNode one = new ListNode();
        ListNode second = new ListNode();
        ListNode oneTail = one;
        ListNode secondTail = second;
        int count = 1;
        while (pre != null){
            if (count % 2 ==1){
                // 说明为奇数
                oneTail.next = pre;
                oneTail = pre;

            }else {
                // 说明为偶数点
                secondTail.next = pre;
                secondTail = pre;
            }
            pre = pre.next;
            count++;
        }
        secondTail.next = null; // 注意这里设置为null，否者形成环状链表了原来4节点后来跟着5节点，合并形成 1 3 5 2 4 5 2 4 5 有一个环
        oneTail.next = second.next;
        return one.next;
    }
}

class Demo328{
  public static void main(String[] args) {
    ListNode head = new ListNode(1);
    head.next = new ListNode(2);
    head.next.next = new ListNode(3);
    head.next.next.next = new ListNode(4);
    head.next.next.next.next = new ListNode(5);
    Test328 t = new Test328();
    ListNode node = t.oddEvenList(head);
    int count = 0;
    while (node!=null){
      System.out.print(node.val+",");
      node = node.next;

    }
  }
}